# -*- coding: utf-8 -*-

"""华沙算法用来计算传递闭包：在一个关系R中，只要 xRy 且 yRz, 那么 xRz。
    按数学规律来讲，如果用邻接矩阵来实现关系，则闭包就是矩阵不断自乘到n次的并集。上述矩阵自乘的算法固然能出结果，但必然存在重复的计算。
    Warshall提出了更好的算法，前提需要将顶点排序，核心是：
        R[k](i,j) = R[k-1](i,j) or ( R[k-1](i,k) and R[k-1](k,j) ), R[k](i,j) 指顶点 i，到 j 经过前面 k 个顶点是否联通。
    这个动态规划的递推公式解释：顶点 i 到 j 经过前面 k 个顶点的是否连通，可由两方面决定：
        其一，顶点 i 到 j 本身经过前面 k-1 个顶点是否连通；其二，顶点 i 到 k 经过前面 k-1 个顶点的连通 合成 顶到 k到 j 经过前面 k-1 个顶点的连通。"""

class Warshall():
    def __init__(self) -> None:
        pass

    def transfer_closure(self, relation: list):
        closure = [list(i) for i in relation]
        count = len(closure)
        for k in range(count):
            for i in range(count):
                for j in range(count):
                    closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])
        return closure


if __name__ == '__main__':
    warshall = Warshall()

    relation = [[0,1,0,0],[1,0,1,0],[0,0,0,1],[0,1,0,0]]
    for i in relation:
        print(i)

    print('计算传递闭包...')
    closure = warshall.transfer_closure(relation)

    for i in closure:
        print(i)
